package com.algorithm.merger;/*
 *@Author:DOWN
 *@Date:2022/1/18 15:16
 *@Comment:
 */

import com.algorithm.testutils.ArrayGenerator;
import com.algorithm.testutils.SortingHelp;

import java.util.Arrays;

public class Solution51 {
    static int pairs = 0;

    public static int reversePairs(int[] nums) {
        pairs = 0;
        int[] temp = new int[nums.length];
        sort(nums, 0, nums.length - 1, 1, temp);
        return pairs;
    }

    private static void sort(int[] arr, int l, int r, int depth, int[] temp) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid, depth + 1, temp);
        sort(arr, mid + 1, r, depth + 1, temp);
        if (arr[mid] > (arr[mid + 1])) {
            merge(arr, l, mid, r, temp);
        }
    }

    private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                pairs += mid - i + 1;
                arr[k] = temp[j];
                j++;
            }
        }
    }
    public static void main(String[] args) {
        Integer[] arrs = ArrayGenerator.getRandomArrays(10000000, 100000);
        int[] arrsc=Arrays.stream(arrs).mapToInt(Integer::intValue).toArray();
        long start = System.nanoTime();
        System.out.println("start:" + start);
        reversePairs(arrsc);
        long end = System.nanoTime();
        System.out.println("end:" + start);
        System.out.println("over:" + (end - start) / 1000000000.0 + "s");
        Integer[] arrs2=Arrays.stream(arrsc).boxed().toArray(Integer[]::new);
        if (SortingHelp.isSorted(arrs2)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
}
